1. Field of the Invention
The present invention relates to virtual Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) systems in mobile multi-hop ad-hoc networks, and relates more specifically to a rate limiting algorithm for distributed contention based transmission protocols without the need of a central controller.
2. Description of the Related Art
Wireless communication networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”. A terrestrial cellular network includes a plurality of interconnected base stations, or base nodes, that are distributed geographically at designated locations throughout the service area. Each base node includes one or more transceivers that are capable of transmitting and receiving electromagnetic signals, such as radio frequency (RF) communications signals, to and from mobile user nodes, such as wireless telephones, located within the coverage area. The communications signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at a first node to communicate simultaneously with several other nodes in its coverage area.
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other mobile nodes, such as those on the public switched telephone network (PSTN), and on other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. Pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, issued on Jul. 4, 2006, in U.S. Pat. No. 6,807,165 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, issued on Oct. 19, 2004, and in U.S. Pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, issued on Mar. 29, 2005, the entire content of each being incorporated herein by reference.
Multiple Access Collision Avoidance (MACA) is a common technique used for mobile multi-hop networks. MACA is described by P. Karn in “MACA—a new channel access method for packet radio,” ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990. It is noted that this reference and all other references cited herein are incorporated by reference herein. The technique described in this cited reference uses reservation messages to avoid packet collisions by using request-to-send (RTS) and clear-to-send (CTS) messages. The transmission between sender and receiver consists of RTS-CTS-DATA messages. MACAW extends MACA by introducing data-sending (DS) and acknowledgment (ACK) messages to form RTS-CTS-DS-DATA-ACK message exchange and a new backoff algorithm. MACAW is further described by V. Bharghavan, A. Demers, S. Shenker, and L. Zhang in “MACAW: A media access protocol for wireless LAN's,” Computer Communication Review, vol. 24, (no. 4), (ACM SIGCOMM '94 Conference on Communications Architectures, Protocols and Applications, London, UK, 31 Aug.-2 Sep. 1994.) October 1994. p. 212-25. Floor Acquisition Multiple Access (FAMA) uses a non-persistent CSMA scheme with RTS/CTS scheme. FAMA is described by C. L. Fullmer, J. J. Garcia-Luna-Aceves, in “Floor acquisition multiple access (FAMA) for packet-radio networks,” Computer Communication Review, vol. 25, (no. 4), (ACM SIGCOMM '95, Cambridge, Mass., USA, 28 Aug.-1 Sep. 1995.) ACM, October 1995. p. 262-73. The IEEE 802.11 MAC is a variation of CSMA/CA protocol that implements both carrier sensing and virtual (RTS-CTS exchange) carrier sensing with acknowledgment messages to improve reliability.
In addition to these messages, the negative-clear-to-send (or not-clear-to-send) (NCTS) message was introduced as an extension to MACA to be used by a central controller such as a base station, to manage the allocation of bandwidth to mobile terminals that require bandwidth guarantees for real-time multimedia data. NCTS is discussed by M. Weiser in “Some Computer Science Issues Related to Ubiquitous Computing,” Comm. ACM, V 36, N 7, July, 1993, pp. 75-85. U.S. Pat. No. 6,404,756 discloses NCTS being used to indicate insufficient signal quality for the requested data rate and insufficient priority for the current message transmission.
U.S. Patent Application No. 20030142645 discloses the use of NCTS for a time division protocol in an ad-hoc network. U.S. Pat. No. 6,556,582 describes a method to avoid multiple access collision in a MACA based wireless network. Unlike the present invention, the collision avoidance scheme is proposed for a system with multiple transceivers, i.e., data channel and reservation channel transceivers. Since the transceivers work simultaneously, NCTS messages are used to inform other nodes that the intended destination node is busy at the current time.
The method described in U.S. Pat. No. 6,556,582 includes also using a priority field in RTS messages. However, processing of this information is based on an absolute comparison, that is, the relative status of the transmissions in the neighborhood is not used.